/**
 * 给定一个矩阵，每一行都是不严格递增的
 * 从每一行选且只选一个数出来，得到一组数并且求和
 * 求这样的第k小的和，最小的和视为第一小 
 * 显然所有开头求和是最小的，但是后续比较麻烦
 * 
 * 定义结构体 {vec, sum}
 * vec记录本次选出的下标，sum记录和
 * 
 * 对sum做一个小根堆，每一次取出堆顶的元素，记作h
 * 则h一共有N个可能的后继可以入队
 * 注意不能重复入队，因此还需要哈希一下
 */
struct _t{
    vector<int> pos;
    int sum;
};

template<> struct std::tr1::hash<_t>{
    static std::size_t splitmix64(std::size_t x){
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);        
    }

    std::size_t operator () (const _t & t) const {
        static const std::size_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        std::size_t h = FIXED_RANDOM;
        for(auto i : t.pos){
            h += i;
            h = splitmix64(h);
        }
        h += t.sum;
        return h = splitmix64(h);
    }
};

template<> struct std::equal_to<_t>{ // 判相等
    bool operator ()  (const _t & lhs, const _t & rhs) const {
        for(int i=0,n=lhs.pos.size();i<n;++i){
            if(lhs.pos[i] != rhs.pos[i]) return false;
        }
        return lhs.sum == rhs.sum;
    }
};

__gnu_pbds::gp_hash_table<_t, unsigned long long> Flag;

class Solution {
    


public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
      
        __gnu_pbds::priority_queue<_t, function<bool(_t, _t)>> Q([](const _t & a, const _t & b)->bool{
            /// 返回真，则a排在底下，b排在堆顶
            if(a.sum != b.sum) return a.sum > b.sum;
            for(int i=0,n=a.pos.size();i<n;++i){
                if(a.pos[i] != b.pos[i]) return a.pos[i] > b.pos[i];
            }
            return false;
        });    

        __gnu_pbds::gp_hash_table<_t, int> Map;

        int sum = 0;
        for(const auto & v : mat) sum += v[0];

        if(1 == k) return sum;

        int Limit = k;
        int N = mat.size();
        int M = mat[0].size();

        Q.push({vector<int>(N, 0), sum});
        Map.insert({_t{vector<int>(N, 0), sum}, 1});

        int ans;
        for(int i=0;i<Limit;++i){
            auto h = Q.top(); Q.pop();
            ans = h.sum;
            for(int j=0;j<N;++j){
                auto idx = h.pos[j];
                if(idx + 1 < M){
                    vector<int> vec(h.pos.begin(), h.pos.end());
                    vec[j] += 1;
                    auto tmp = h.sum - mat[j][vec[j] - 1] + mat[j][vec[j]];
                    auto it = Map.find({vec, tmp});
                    if(it == Map.end()){
                        Map.insert({{_t{vec, tmp}}, 1});
                        Q.push({vec, tmp});
                    }                   
                }
            }
        }
        return ans;
    }
};